package number_146;


import java.util.HashMap;
import java.util.Map;

public class LRUCache {
    private int capacity;
    private int size;
    private EntryNode head;
    private EntryNode tail;
    private Map<Integer, EntryNode> cacheMap;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new EntryNode();
        tail = new EntryNode();
        head.next = tail;
        tail.prev = head;
        cacheMap = new HashMap<>();
    }

    public int get(int key) {
        EntryNode node = cacheMap.get(key);
        if (node == null) {
            return -1;
        }
        moveToHead(node);
        return node.value;
    }

    private void moveToHead(EntryNode node) {
        removeNode(node);
        addToHead(node);
    }

    private void addToHead(EntryNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(EntryNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    public void put(int key, int value) {
        EntryNode node = cacheMap.get(key);
        if (node == null) {
            size++;
            node = new EntryNode(key, value);
            addToHead(node);
            cacheMap.put(key, node);
            if (size > capacity) {
                EntryNode removeNode = removeTail();
                cacheMap.remove(removeNode.key);
                size--;
            }
        } else {
            node.value = value;
            moveToHead(node);
        }

    }

    private EntryNode removeTail() {
        EntryNode node = tail.prev;
        removeNode(node);
        return node;
    }

    class EntryNode {
        int key;
        int value;
        EntryNode prev;
        EntryNode next;

        public EntryNode() {
        }

        public EntryNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
}
